一道并不难的 题。转移式很好列:
看到区间的最大值与最小值之差,我们很容易想到用 表维护。这样可以解决。
很显然的一个结论是,决策点是单调递增的。因为 不断向右,区间的最值递增,决策点也必须向右调整。
并且,为了使答案更优,我们每次一定会选择最靠左的那个决策点。
所以,只需要维护最左边的决策点即可,转移复杂度。
总时间复杂度
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define INF 0x3f3f3f3f
const int MAXN = 100000 , MAXK = 20;
int n , l , s , a[ MAXN + 5 ] , f[ 2 ][ MAXN + 5 ][ MAXK + 5 ]; //0->max 1->min
int dp[ MAXN + 5 ];
void Init( ) {
memset( f[ 1 ] , 0x3f , sizeof( f[ 1 ] ) );
for( int i = 1 ; i <= n ; i ++ )
f[ 0 ][ i ][ 0 ] = f[ 1 ][ i ][ 0 ] = a[ i ];
for( int j = 1 ; ( 1 << j ) <= n ; j ++ )
for( int i = 1 ; i + ( 1 << j ) - 1 <= n ; i ++ ) {
f[ 0 ][ i ][ j ] = max( f[ 0 ][ i ][ j - 1 ] , f[ 0 ][ i + ( 1 << j - 1 ) ][ j - 1 ] );
f[ 1 ][ i ][ j ] = min( f[ 1 ][ i ][ j - 1 ] , f[ 1 ][ i + ( 1 << j - 1 ) ][ j - 1 ] );
}
}
int Query( int l , int r ) {
int k = log2( r - l + 1 );
return max( f[ 0 ][ l ][ k ] , f[ 0 ][ r - ( 1 << k ) + 1 ][ k ] ) - min( f[ 1 ][ l ][ k ] , f[ 1 ][ r - ( 1 << k ) + 1 ][ k ] );
}
int main( ) {
scanf("%d %d %d",&n,&s,&l);
for( int i = 1 ; i <= n ; i ++ )
scanf("%d",&a[ i ]);
Init( );
memset( dp , 0x3f , sizeof( dp ) ); dp[ 0 ] = 0;
int chk = 0;
for( int i = l ; i <= n ; i ++ ) {
while( ( i - chk >= l && ( Query( chk + 1 , i ) > s ) || dp[ chk ] == INF ) ) chk ++;
if( i - chk >= l ) dp[ i ] = dp[ chk ] + 1;
}
printf("%d", dp[ n ] == INF ? -1 : dp[ n ] );
return 0;
}